﻿namespace LeetCodeProject._0001_1000._001_100._21_30._030;

public class Solution
{
    public IList<int> FindSubstring(string s, string[] words)
    {
        IList<int> res = new List<int>();
        int m = words.Length, n = words[0].Length, ls = s.Length;
        for (int i = 0; i < n; i++)
        {
            if (i + m * n > ls)
            {
                break;
            }

            Dictionary<string, int> differ = new Dictionary<string, int>();
            for (int j = 0; j < m; j++)
            {
                string word = s.Substring(i + j * n, n);
                if (!differ.ContainsKey(word))
                {
                    differ.Add(word, 0);
                }

                differ[word]++;
            }

            foreach (string word in words)
            {
                if (!differ.ContainsKey(word))
                {
                    differ.Add(word, 0);
                }

                differ[word]--;
                if (differ[word] == 0)
                {
                    differ.Remove(word);
                }
            }

            for (int start = i; start < ls - m * n + 1; start += n)
            {
                if (start != i)
                {
                    string word = s.Substring(start + (m - 1) * n, n);
                    if (!differ.ContainsKey(word))
                    {
                        differ.Add(word, 0);
                    }

                    differ[word]++;
                    if (differ[word] == 0)
                    {
                        differ.Remove(word);
                    }

                    word = s.Substring(start - n, n);
                    if (!differ.ContainsKey(word))
                    {
                        differ.Add(word, 0);
                    }

                    differ[word]--;
                    if (differ[word] == 0)
                    {
                        differ.Remove(word);
                    }
                }

                if (differ.Count == 0)
                {
                    res.Add(start);
                }
            }
        }

        return res;
    }
}